package org.algorithm.wE1.数组.三月.第三周;

/**
 * @date 2022-03-18 星期五17:33
 *
 * url:  https://leetcode-cn.com/problems/best-sightseeing-pair/
 */
public class 最佳观光组合 {

    public static void main(String[] args) {
        int[] nums = {8,1,5,2,6};
        System.out.println(maxScoreSightseeingPair(nums));
    }

    /**
     *
     * 输入：values = [8,1,5,2,6]
     * 输出：11
     * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
     *
     */
    public static int maxScoreSightseeingPair(int[] values) {
        if(values == null || values.length<2){
            return 0;
        }
        /**
         * values[i] + values[j] + i - j = values[i]+i  + (values[j]-j)
         * 因为 j>i 所以 在每层遍历 j不变 找j之前所有的景点 中找到 最大的 value[i]+i
         */
        int ans = 0;
        int mx = values[0];
        for (int j = 1; j < values.length; j++) {
            ans = Math.max(ans,mx+values[j] - j);
            //j之前 最大的 value[i]+i
            mx = Math.max(mx,values[j]+j);
        }
        return ans;
    }


//    public static int maxScoreSightseeingPair(int[] values) {
//        if(values == null || values.length<2){
//            return 0;
//        }
//        int ans = 0;
//        for (int i = 0; i < values.length; i++) {
//            for (int j = i+1; j <values.length ; j++) {
//                ans = Math.max(ans,values[i]+values[j]+i-j);
//            }
//        }
//        return ans;
//    }

}
